home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 8489 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  4.2 KB
  1. Path: mail2news.demon.co.uk!tsys.demon.co.uk
  2. From: Tom Wheeley <tomw@tsys.demon.co.uk>
  3. Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: Thu, 15 Feb 96 23:26:20 GMT
  6. Organization: City Zen FM
  7. Message-ID: <824426780snz@tsys.demon.co.uk>
  8. References: <4fr8be$ass@news.iconn.net> <31224679.6193@born.com> <4fv74c$chq@gatekeeper.alcatel.no>
  9. Reply-To: tomw@tsys.demon.co.uk
  10. X-NNTP-Posting-Host: tsys.demon.co.uk
  11. X-Newsreader: Demon Internet Simple News v1.30
  12. X-Sig-By: Tomsystems Quote v1.2.  (c)1996 Tom Wheeley, tomw@tsys.demon.co.uk
  13. X-Mail2News-Path: tsys.demon.co.uk
  14.  
  15. In article <4fv74c$chq@gatekeeper.alcatel.no>
  16.            Sven.Pran@alcatel.no "Sven Pran" writes:
  17.  
  18. > In article <31224679.6193@born.com>, John Cleland <clelaj@born.com> wrote:
  19. > >The Crow wrote:
  20. > >> 
  21. > >> Here is what I am trying to do, I want to find the last NON-ZERO digit of a
  22. > >> given factorial.  For instance,
  23. > >> 
  24. > >> 5! = 120
  25. > >> 
  26. > >> so the last non-zero digit is 2.  I want to be able to do this up to 1000.
  27. > >> Problem is, no matter how huge of a data-type you use, there isn't any way 
  28. > >> for the computer to handle 1000!, it is however possible to find the last 
  29. > >> non-zero digit somehow.  One thing I have tried is as I went through 
  30. > >> multiplying the series of numbers in the factorial (5 * 4 * 3 * 2) I would 
  31. > >> remove all the trailing ZEROS, I got this to work up to 789, but it wont 
  32. > >> work with 1000 and i am not really sure why.  If anyone has a clue how I 
  33. > >> can do this let me know.
  34. > >
  35. > >Don't just strip the trailing zeros, remove all digits except the last 
  36. > >non-zero digit (which is your output) and then multiply by the next number in 
  37. > >your sequence. This keeps the numbers down to a managable level and gives the 
  38. > >correct answer as no more significant digit can affect the value of the LSD.
  39. > >
  40. >  . . . .
  41. > 
  42. > No, it is obviously not sufficient to keep the last single non-zero digit, and 
  43. > the problem appears to be a very interesting and intriguing one:
  44. > 
  45. > A new trailing zero is 'created' every time the next multiplier is divisible 
  46. > by 5, and how can we then calculate the next 'rightmost significant' digit?
  47. > 
  48. > Example when a multiplier ends in 05:
  49. > 
  50. > If the 'previous' factorial ended in 02 then the new factorial will end in 1 
  51. > while if it ended in 12 then the new factorial will end in 6 (after removal of 
  52. > trailing zeroes).
  53. > 
  54. > Thus the SINGLE rightmost significant digit in the new factorial depends upon 
  55. > the TWO rightmost significant digits both in the previous factorial and in the 
  56. > multiplier.
  57. > 
  58. > This means that we must keep track of the last TWO digits to calculate the new 
  59. > SINGLE rightmost significant digit whenever a zero is 'created'. For similar 
  60. > reasons we must track THREE digits to calculate the new TWO rightmost 
  61. > significant digits - and so on.
  62. > 
  63. > How many zeroes have been 'removed' when we reach 1000! ? The answer is 249, 
  64. > which means that in order to maintain the precision needed we must track the 
  65. > last 250 digits less the number of zeroes already 'removed' when N! reaches a 
  66. > number with that many digits.
  67.  
  68. Yes, but these digits are the rightmost when we throw them away as we go along.
  69. Remember that our running total is not affected by itself, so we can throw away
  70. the bits we don't want.  This includes a trailing 0.
  71.  
  72. Using this method would give simple to program results for n up to the maximum
  73. size of a long integer / 9.  More if you do your own multiplication:
  74.  
  75. let t be 1.
  76. Run a loop for variable r from 2 to n.  (for loop...)
  77.   Multiply t by r.
  78.   Strip trailing zeros.
  79.   Take rightmost digit, and put it in t.
  80. loop round.
  81.  
  82. t is your answer.
  83.  
  84. (Crossposted to C and Pascal, so written in English :)
  85.  
  86. Basically, you must remember that all the other information stored in t is
  87. irrelevant.  It is only ever the last digit which determines what the next
  88. last digit will be.
  89.  
  90. In fact, you could just sum the digits of r and multiply t by that.  You could
  91. then perhaps store the digits of r in an array, allowing for large values
  92. of n.  (Multiply, add, trim; Multiply, add, trim; through the digits)
  93.  
  94. I suspect there will be a flaw in my reasoning, so feel free to point it out :)
  95. -- 
  96. * TQ 1.0 * The 'Just So Quotes'.
  97. Sic Biscuitus Disintegrat.
  98.         -- Adrian Ogden
  99.